package leetcode.other.divide_and_conquer;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/7/3 17:49
 */
public class 大数乘法 {
    public static void main(String[] args) {
        System.out.println(multiply("999", "999"));
    }

    public static String multiply(String num1, String num2) {
        if (num1 == null || num2 == null) return null;
        if (num1.equals("0") || num2.equals("0")) return "0";
        // 123 * 456
        int[] res = new int[num1.length() + num2.length()];
        // 遍历3 2 1
        for (int i = num1.length() - 1; i > -1; i--) {
            int n1 = num1.charAt(i) - '0';
            // 遍历6 5 4
            for (int j = num2.length() - 1; j > -1; j--) {
                int n2 = num2.charAt(j) - '0';
                // n1 = 3, n2 = 6, i = 2, j = 2
                int sum = res[i + j + 1] + n1 * n2;
                // sum = 0 + 3 * 6 = 18
                // 相乘后的个位数，也是 i + j + 1 索引 = 18 % 10 = 8
                res[i + j + 1] = sum % 10;
                // 相乘后的十位数，也是数组中的 i + j 索引 = 18 / 10 = 1
                res[i + j] += sum / 10;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            if (i == 0 && res[i] == 0) continue;
            sb.append(res[i]);
        }
        return sb.toString();
    }
}
